package com.dushougudu;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Author zhangtao
 * @create 2021/12/17 15:59
 */
public class Solution {
    public static String longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        int index = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '>') {
                if (s.charAt(i - 1) == '<') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '<') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                if (maxans < dp[i]) {
                    index = i;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return s.substring(index - maxans + 1, index + 1);
    }

    public static int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int ret = 0;
        Map<Integer, String> result = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            if (ret >= n - i || ret > n / 2) {
                break;
            }
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            Map<Integer, Integer> amap = new HashMap<Integer, Integer>();
            for (int j = i + 1; j < n; j++) {
                int gcdXY = 0;
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    gcdXY = gcd(Math.abs(x), Math.abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                int key = y + x * 20001;
                map.put(key, map.getOrDefault(key, 0) + 1);
                amap.put(key, gcdXY);
                if (key == 20004) {
                    System.out.println("x:" + points[i][0] + " y:" + points[i][1]);
                    result.put(points[i][0], "[" + points[i][0] + "," + points[i][1] + "]");
                }
            }
            int maxn = 0;
            int key = 0;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int num = entry.getValue();
                if (num > maxn) {
                    key = entry.getKey();
                }
                maxn = Math.max(maxn, num + 1);
            }
            if (maxn > ret) {
                System.out.println(key);
            }
            ret = Math.max(ret, maxn);

        }
        for (Map.Entry<Integer, String> s : result.entrySet()) {
            System.out.print(s.getValue());
            System.out.print(",");
        }
        return ret;
    }

    public static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }


    public static int maxPoints1(int[][] points) {
        int res = 1;
        Map<String, String> result = new TreeMap<>();
        for (int i = 0; i < points.length; ++i) {
            int[] m = points[i];
            for (int j = i + 1; j < points.length; ++j) {
                int dx = points[j][0] - m[0];
                int dy = points[j][1] - m[1];
                int count = 0;
                int d = dx * m[1] - dy * m[0];
                for (int[] p : points) {
//                  化简得来
                    if (dx * p[1] == dy * p[0] + d)
                        ++count;
                }
                if (count == 10) {//y=3x+7
                    System.out.println("x:" + m[0] + " y:" + m[1]);
                    result.put("[" + m[0] + "," + m[1] + "]", "[" + m[0] + "," + m[1] + "]");
                }
                res = Math.max(res, count);
            }
        }
        for (Map.Entry<String, String> s : result.entrySet()) {
            System.out.print(s.getValue());
            System.out.print(",");
        }
        return res;
    }

    public static void main(String[] args) {
//        System.out.println(longestValidParentheses(">>><<><<<>>><<<<<<>><<<><><><<<<>><<>>>><>>><<>>><<>>>>><><<><><<>>><><<<<><>><>><>>><<<><<<<>>><<<<<>><<<<<<>>><<<<>>>>><>>>><<<><>><<>>>>><<<>><>><><><>><<>>>>>>>>><>>>><<><>><<<<<<<>>><<<>>><>><<<>><>>>>><>><>>><<<>>><<>><><><>>><<<<><><<<><><<>><<>>><>>>>><>>>><<<<><><<<<>><>><<>><><<><<<<<<<><>>>><<<>>>><>>><<>>><<<><<>><<<<<<>><><<><><>><<<<><<><>><><<><><>>>><<>>>><<>><><><<>><<><<><<<<>>>><<<><><<><>>><<><><<<<<<>>>>>><><><><<>><><<<>>>><>>><<>>><>><<<><<<<<<>>>>><>><><<>>>><>><<><><<><<<<<>>>>><<>><<<>><<><<><<<<<<><>>><<<>>>><<<>><<>><<>>>>><><>><>><><<<>>><>><<<<<>>>><<<>><<><>>><><><<<<><><<<><<<>>>><<><<><><>>>><><<><>>>><><><><<>><>><><<<><<>><<<<><<<<><<<<>><><<<<<<<>>>>>><>>>><><<>>>><>>>>>>><<<><<<>><>>>>><<<><><>>><>><>>>><<><<<<><>><><<<<>>>><<<><<<>><<><>>>><><<>>><<>><<<<><><>><<<><><<>>><<><><<><<>><>><<<<>><<><<><<<<><<>><><><<><>>><>><>>>>><>><><><>><<<>>>>><<><<<<>><<><><>>><>>><>>>><<<><>>><<<><<>>><<>>>>>>><<>>><<>>>>>>><<<<<<>><><<>><<>><<>>>><>><><<<<>><><<><<>>>>><><>>><>>><>>>><<<>><><><<>>>>><>>>><<>>><<>><><<>>><>><<><><><<><><><>><><><><<<<><>>><>>><><<<>><><<>>><><><<<><<<><>><>>><<<<<><<><>><>>><><><<<<<<<>>><>><><<<<<<>>>><><<>>><<><<><>><><>><><><<<><>>>>>>>>><><<<<<<<<<<<<>>>>>>><<<>><<><>><<>><>><<>>>><>>><<>><<<>><><><><<<<<<>><>><><<<>>>><<<>><<>>><<<><>>>><<<<<>><><>><<>><<<>><<>>><>><<>><<<<>>><<<>>><<>><<<>><>>><<<<<>>>><><>><<><><<>><<>>><><>>>>><<<>>>>>><<<><<<><<<<>>>>>>><>>>><>>><<>><><<><<<<>>>><><<>>>>><<>><>><<<<<<<<>>>>><<<<<<><<<<>><>>><><<<<>>>>>><><><>><<>>>><<<<>><>><<>><<<>>><>><>><><><><<<<>><<><><<><>><><<<><><<<>><><>><>>>><<<>><<<>>>>>><>>>><<<>>><>>>><<<<<><<<<<<<<<<><<<<>><><><<<>>>><>><>><><>>><>><<<><><><>><<><<<<<><<>><>><><><<<<>><<>><>>><>>><><>>><>><><>><><>>>>><<>>>>>><<>><<<>>><<<><><><<>>><>>>><>><><<>><<><<><<><>><<>><><>>><<>>><<><><<<<<<<<>><><><<><>><<<<>>><<<><>><<>><><>><><<><>><>><<<<><><<<><>><<<<<>><<<<><><><<>><<<><>><>><>>>>>><<><<><>><>>>><>>>><>><<<><<<><><>><<<><<<<<<<<<>><<><>><>"));
        String aa = "[105, 339], [662, 97], [689, 110], [420, 544], [558, 151], [901, 99], [759, 516], [286, 788], [543, 512], [945, 601], [357, 206], [645, 211], [422, 547], [768, 939], [761, 306], [980, 243], [255, 633], [404, 306], [325, 960], [986, 857], [808, 810], [894, 651], [436, 844], [316, 546], [345, 218], [835, 844], [322, 441], [542, 285], [955, 647], [72, 245], [334, 246], [369, 90], [226, 432], [807, 480], [114, 413], [227, 413], [877, 695], [378, 402], [350, 878], [364, 635], [162, 712], [404, 351], [338, 160], [316, 386], [300, 391], [701, 784], [26, 936], [312, 405], [871, 93], [28, 168], [849, 664], [460, 998], [592, 868], [84, 402], [593, 553], [448, 482], [503, 854], [329, 597], [999, 304], [349, 848], [494, 617], [410, 856], [641, 700], [47, 721], [337, 789], [54, 853], [81, 957], [722, 817], [397, 27], [337, 769], [465, 807], [294, 156], [875, 935], [654, 266], [342, 796], [660, 1], [435, 599], [563, 735], [406, 669], [512, 578], [531, 162], [642, 3], [308, 522], [695, 954], [720, 546], [28, 634], [737, 620], [744, 381], [881, 329], [318, 978], [986, 49], [837, 426], [57, 391], [229, 499], [422, 768], [240, 884], [835, 962], [827, 455], [774, 96], [104, 340], [109, 635], [169, 594], [493, 573], [627, 992], [479, 263], [765, 714], [912, 787], [43, 351], [819, 979], [691, 719], [821, 696], [995, 402], [884, 175], [77, 52], [733, 510], [433, 916], [945, 828], [589, 516], [963, 782], [579, 619], [976, 365], [679, 605], [196, 365], [212, 68], [101, 729], [442, 80], [718, 586], [894, 602], [418, 383], [909, 30], [299, 789], [462, 238], [862, 775], [260, 956], [981, 10], [260, 40], [249, 95], [761, 479], [913, 3], [666, 316], [219, 220], [237, 344], [358, 249], [162, 278], [738, 780], [791, 249], [133, 324], [667, 262], [810, 770], [360, 654], [504, 637], [122, 348], [940, 241], [743, 125], [764, 107], [522, 517], [226, 791], [40, 5], [329, 914], [142, 186], [742, 956], [269, 522], [246, 261], [252, 776], [872, 400], [624, 567], [343, 84], [681, 506], [287, 359], [260, 546], [273, 662], [337, 137], [444, 600], [568, 691], [746, 144], [869, 564], [412, 689], [93, 84], [395, 900], [284, 695], [500, 940], [821, 330], [599, 219], [397, 472], [221, 925], [740, 458], [835, 674], [769, 500], [847, 842], [480, 732], [918, 248], [659, 246], [167, 561], [91, 923], [8, 974], [169, 9], [147, 460], [237, 275], [20, 333], [186, 880], [802, 320], [316, 553], [807, 619], [31, 268], [702, 912], [469, 14], [736, 110], [755, 917], [595, 582], [690, 844], [936, 382], [925, 599], [487, 363], [115, 862], [113, 343], [299, 367], [170, 930], [991, 468], [849, 932], [631, 635], [709, 496], [50, 572], [29, 381], [203, 125], [484, 230], [718, 386], [280, 409], [342, 704], [286, 717], [500, 664], [427, 612], [950, 273], [289, 552], [185, 166], [140, 282], [732, 687], [280, 349], [252, 419], [105, 41], [725, 370], [926, 500], [380, 537], [667, 227], [806, 191], [314, 598], [571, 132], [878, 57], [133, 626], [155, 446], [591, 27], [909, 464], [756, 353], [435, 603], [190, 877], [960, 95], [607, 200], [838, 828], [511, 597], [143, 863], [138, 655], [969, 458], [93, 550], [821, 409], [13, 157], [685, 224], [348, 999], [591, 435], [466, 864], [899, 358], [4, 736], [861, 211], [563, 434], [383, 217], [11, 779], [934, 937], [510, 157], [422, 508], [765, 659], [837, 465], [338, 655], [938, 27], [773, 751], [840, 614], [665, 167], [162, 610], [386, 615], [357, 496], [446, 917], [332, 993], [965, 422], [276, 158], [126, 365], [933, 482], [855, 110], [186, 604], [288, 180], [613, 305], [37, 406], [626, 678], [71, 657], [102, 651], [414, 911], [659, 402], [940, 709], [923, 407], [528, 482], [487, 346], [230, 691], [347, 407], [512, 299], [863, 591], [427, 544], [420, 7], [713, 353], [377, 622], [510, 771], [914, 621], [209, 27], [508, 879], [145, 733], [127, 759], [97, 395], [440, 864], [466, 538], [690, 55], [875, 31], [625, 774], [15, 782], [475, 610], [492, 42], [674, 667], [707, 697], [786, 828], [433, 463], [244, 888], [97, 811], [757, 245], [875, 862], [358, 581], [381, 487], [72, 110], [701, 556], [428, 491], [16, 596], [388, 604], [714, 87], [865, 785], [802, 542], [58, 644], [489, 431], [822, 291], [584, 385], [463, 557], [683, 246], [699, 180], [637, 294], [568, 8], [897, 984], [963, 773], [242, 836], [164, 243], [664, 67], [354, 843], [399, 512], [119, 265], [150, 808], [391, 740], [785, 156], [515, 395], [36, 712], [660, 58], [780, 67], [110, 146], [571, 47], [539, 238], [936, 259], [488, 865], [897, 43], [104, 765], [54, 761], [619, 415], [771, 301], [347, 822], [970, 184], [283, 659], [818, 510], [77, 626], [656, 130], [366, 814], [880, 547], [719, 346], [104, 84], [931, 412], [297, 538], [408, 84], [771, 38], [244, 618], [109, 26], [766, 630], [661, 64], [693, 89], [114, 822], [281, 385], [267, 542], [324, 689], [555, 338], [644, 447], [556, 893], [497, 590], [853, 764], [629, 340], [626, 931], [797, 822], [374, 652], [259, 336], [568, 170], [196, 825], [39, 579], [717, 162], [330, 660], [165, 271], [825, 87], [534, 166], [186, 960], [382, 749], [401, 133], [805, 912], [767, 563], [378, 535], [709, 765], [446, 374], [517, 16], [948, 287], [381, 194], [212, 826], [170, 112], [483, 652], [549, 295], [689, 957], [660, 818], [70, 403], [567, 250], [385, 773], [245, 532], [399, 314], [20, 939], [669, 991], [857, 287], [810, 455], [297, 142], [251, 52], [5, 406], [156, 52], [619, 676], [616, 448], [567, 199], [54, 302], [910, 78], [208, 78], [98, 472], [576, 873], [759, 538], [258, 501], [88, 986], [360, 933], [999, 875], [958, 677], [752, 361], [963, 684], [168, 332], [544, 18], [591, 906], [536, 609], [487, 869], [828, 32], [680, 219], [2, 33], [10, 868], [289, 804], [30, 7], [924, 61], [314, 53], [137, 49], [286, 7], [332, 566], [983, 42], [340, 760], [64, 776], [2, 975], [632, 339], [842, 182], [661, 307], [120, 695], [50, 151], [64, 321], [519, 768], [961, 643], [886, 344], [207, 611], [389, 874], [67, 487], [141, 291], [538, 493], [606, 213], [175, 30], [565, 125], [181, 805], [27, 291], [205, 461], [387, 518], [305, 528], [567, 274], [283, 652], [783, 657], [308, 839], [208, 886], [85, 268], [141, 362], [227, 278], [509, 757], [843, 697], [32, 318], [490, 496], [991, 638], [455, 16], [623, 70], [736, 620], [290, 185], [766, 730], [210, 587], [654, 170], [418, 409], [20, 351], [556, 571], [62, 630], [544, 988], [130, 340], [320, 746], [901, 428], [613, 465], [98, 373], [932, 386], [323, 257], [427, 64], [350, 674], [35, 131], [583, 408], [593, 237], [422, 758], [940, 978], [717, 418], [349, 701], [817, 386], [462, 334], [594, 348], [913, 408], [944, 166], [574, 374], [812, 309], [152, 645], [184, 417], [140, 188], [92, 292], [911, 344], [646, 883], [908, 420], [925, 37], [767, 182], [514, 129], [296, 685], [812, 133], [463, 878], [910, 361], [856, 870], [663, 321], [931, 154], [942, 929], [876, 922], [136, 899], [42, 620], [392, 972], [701, 724], [561, 804], [809, 633], [3, 948], [306, 731], [607, 770], [818, 216], [89, 464], [902, 55], [337, 883], [50, 420], [870, 743], [508, 393], [872, 680], [756, 21], [592, 419], [638, 302], [838, 923], [536, 875], [255, 63], [246, 620], [449, 800], [320, 579], [548, 857], [917, 195], [134, 119], [239, 742], [715, 632], [778, 621], [784, 560], [658, 361], [530, 638], [808, 575], [832, 781], [368, 31], [970, 414], [91, 541], [388, 467], [140, 496], [459, 110], [384, 689], [114, 960], [951, 430], [257, 550], [978, 571], [819, 798], [72, 258], [187, 639], [945, 713], [594, 358], [782, 778], [912, 421], [522, 433], [669, 974], [641, 454], [66, 885], [988, 482], [552, 835], [54, 158], [972, 503], [143, 990], [286, 431], [970, 629], [349, 700], [84, 275], [194, 19], [452, 569], [53, 56], [865, 468], [375, 933], [805, 672], [981, 577], [948, 260], [901, 203], [520, 995], [289, 261], [997, 155], [53, 366], [948, 334], [486, 40], [502, 910], [913, 880], [766, 374], [405, 19], [324, 995], [519, 845], [794, 905], [376, 965], [300, 82], [341, 101], [817, 601], [738, 358], [8, 893], [451, 704], [889, 121], [313, 62], [210, 336], [270, 336], [970, 277], [829, 410], [78, 377], [41, 546], [237, 806], [96, 431], [369, 360], [243, 277], [13, 443], [829, 284], [86, 976], [837, 880], [735, 321], [306, 132], [853, 715], [19, 632], [267, 236], [712, 449], [619, 410], [968, 799], [170, 891], [903, 578], [887, 826], [172, 589], [400, 375], [37, 317], [792, 496], [911, 403], [289, 547], [910, 965], [570, 430], [204, 235], [837, 869], [682, 212], [776, 690], [9, 209], [229, 587], [227, 553], [472, 541], [147, 116], [69, 743], [110, 84], [204, 329], [636, 341], [666, 435], [391, 388], [781, 18], [847, 549], [771, 53], [655, 303], [328, 630], [599, 163], [914, 428], [167, 298], [298, 892], [741, 36], [418, 456], [84, 628], [229, 384], [161, 400], [247, 445], [691, 367], [251, 157], [206, 548], [499, 616], [339, 895], [367, 113], [328, 914], [525, 856], [759, 728], [57, 284], [790, 945], [897, 582], [371, 699], [680, 488], [970, 539], [621, 652], [676, 913], [703, 402], [93, 217], [127, 833], [187, 646], [250, 871], [222, 929], [562, 812], [504, 143], [224, 520], [290, 176], [695, 844], [800, 996], [936, 638], [402, 32], [510, 302], [224, 502], [309, 725], [466, 99], [164, 198], [913, 753], [940, 908], [357, 973], [220, 59], [684, 739], [219, 171], [964, 725], [425, 119], [189, 939], [641, 884], [758, 964], [567, 589], [874, 266], [210, 467], [359, 931], [567, 985], [3, 468], [186, 53], [387, 33], [593, 995], [529, 824], [678, 700], [497, 539], [809, 715], [120, 283], [472, 768], [698, 938], [92, 78], [606, 617], [242, 783], [696, 928], [458, 167], [724, 860], [903, 741], [274, 698], [651, 902], [346, 842], [751, 92], [956, 287], [68, 652], [532, 778], [177, 557], [649, 206], [857, 828], [25, 959], [472, 341], [611, 380], [234, 700], [592, 227], [688, 393], [470, 547], [543, 929], [91, 213], [503, 777], [530, 500], [726, 190], [333, 907], [22, 216], [512, 501], [970, 861], [941, 520], [888, 329], [818, 723], [282, 859], [403, 462], [127, 371], [132, 697], [546, 32], [672, 925], [636, 590], [287, 366], [115, 836], [671, 674], [885, 404], [482, 803], [138, 387], [144, 104], [62, 120], [209, 938], [384, 673], [137, 530], [947, 369], [424, 840], [30, 767], [797, 182], [377, 312], [414, 955], [766, 715], [271, 771], [450, 573], [173, 515], [919, 971], [29, 147], [615, 373], [613, 220], [543, 387], [599, 721], [358, 134], [438, 899], [624, 513], [390, 212], [35, 777], [188, 916], [797, 471], [599, 546], [512, 559], [498, 762], [827, 865], [304, 29], [895, 204], [194, 470], [35, 146], [631, 145], [780, 439], [625, 886], [92, 435], [848, 539], [789, 743], [253, 496], [475, 660], [469, 595], [43, 791], [344, 795], [620, 272], [317, 114], [753, 610], [652, 812], [535, 133], [255, 228], [937, 111], [494, 262], [518, 337], [734, 951], [196, 325], [37, 496], [19, 606], [284, 562], [136, 64], [625, 875], [196, 382], [808, 158], [409, 26], [486, 689], [281, 558], [250, 864], [42, 178], [744, 903], [394, 903], [443, 988], [226, 192], [479, 963], [106, 520], [832, 155], [690, 638], [666, 669], [320, 973], [118, 277], [299, 16], [117, 122], [843, 459], [84, 271], [690, 668], [92, 572], [363, 16], [181, 478], [910, 795], [951, 227], [901, 495], [853, 834], [166, 717], [214, 70], [965, 610], [393, 804], [844, 40], [588, 650], [586, 710], [753, 687], [678, 522], [886, 241], [983, 986], [680, 946], [970, 594], [491, 852], [622, 927], [264, 899], [263, 786], [939, 770], [821, 648], [31, 405], [480, 295], [849, 789], [202, 75], [78, 883], [473, 567], [634, 436], [432, 31], [990, 954], [714, 505], [349, 3], [866, 828], [211, 898], [1, 32], [746, 308], [325, 125], [931, 517], [146, 40], [78, 825], [871, 944], [981, 510], [368, 735], [283, 198], [76, 492], [836, 27], [866, 269], [433, 523], [645, 145], [268, 659], [801, 331], [754, 696], [664, 867], [281, 856], [334, 295], [999, 463], [981, 631], [100, 307], [574, 1729], [230, 697], [622, 1873], [102, 313], [198, 601], [549, 1654], [188, 571], [815, 2452], [730, 2197]";
        String[] ii = aa.split("],");
        int[][] intarray = new int[ii.length][2];
        Map<String, String> result = new TreeMap<>();
        for (int i = 0; i < ii.length; i++) {

            String[] arry = ii[i].replace("]", "").replace("[", "").replace(" ", "").split(",");
            intarray[i][0] = Integer.parseInt(arry[0]);
            intarray[i][1] = Integer.parseInt(arry[1]);

            if (intarray[i][1] == 3 * intarray[i][0] + 7){
                result.put("[" + intarray[i][0] + "," + intarray[i][1] + "]", "[" + intarray[i][0] + "," + intarray[i][1] + "]");
            }
        }
        for (Map.Entry<String, String> s : result.entrySet()) {
            System.out.print(s.getValue());
            System.out.print(",");
        }
//        System.out.println(maxPoints1(intarray));
    }
}